The present invention relates to matrix decomposition.
It is sometimes desirable to decompose a matrix A into other matrices. There are many types of matrix decomposition, an example of which is Cholesky decomposition. In Cholesky decomposition a positive definite matrix A is factorized into matrices L and LH such that:A=LLH,where L is a lower triangular matrix having positive values on its diagonal, and LH is the Hermitian transpose of L.
While positive-definite matrices are special, they are quite frequent in wireless communication applications. Their factorization is therefore of some interest. Decomposing A into a lower (and upper) triangular matrix can be useful when solving simultaneous equations. L and LH can be used in forward and backward substitution to obtain the coefficient values.
Below is a general outline of the steps of the Cholesky algorithm for decomposing an input matrix A into an output matrix L. In the below description, aij refers to an element of the matrix A in row i and column j, lij refers to an element of the matrix L in row i and column j, elements of either matrix where i is equal to j are referred to as diagonal elements, and i and j are non-zero positive integers that range from 1 to n (where n is an integer representing the size of the matrices A and L). The general steps of the Cholesky algorithm are as follows:
1. Set all elements of L above the main diagonal equal to zero;
2. Set l11=√{square root over (a11)};
3. Generate the remaining values of column 1 as: li1=ai1/l11;
4. Set j=2;
5. IF j=n+1 THEN
                Stop; (algorithm completed)        
ELSE                Define L′i to be a column vector of dimension j−1 whose components are the first j−1 elements in the ith row of L;        
END IF                (i=j, j+1, j+2, . . . , n);6. Calculate jth column of L;        
IF i=j THEN // Calculate diagonal elementljj=√{square root over (ajj−L′j,L′j)};
(where L′j,L′j denotes the inner product of vectors L′j and L′j)
ELSE // Calculate non-diagonal elementlij=(aij−L′i,L′j)/ljj;
END IF i=(j, j+1, . . . , n);
7. Increment j; and
8. Go to step 5
The above method essentially involves the following. For each column of L, starting from the first column and proceeding to the other columns in order of increasing column number, the diagonal element and then the non-diagonal elements are calculated. The non-diagonal elements are calculated starting with the non-diagonal element immediately below the diagonal element and proceeding down the column in order of increasing row numbers. Once both the diagonal and all non-diagonal elements for a column are calculated, the process proceeds to calculating the diagonal and non-diagonal elements of the next column. This process is continued until the elements of all columns of L are calculated.
As an example, the calculations required for decomposing a 4 by 4 input matrix A into a 4 by 4 output matrix L are listed below. Input matrix A and output matrix L have the following general form:
                    A        =                  (                                                                      a                  11                                                                              a                  12                                                                              a                  13                                                                              a                  14                                                                                                      a                  21                                                                              a                  22                                                                              a                  23                                                                              a                  24                                                                                                      a                  31                                                                              a                  32                                                                              a                  33                                                                              a                  34                                                                                                      a                  41                                                                              a                  42                                                                              a                  43                                                                              a                  44                                                              )                                    L        =                  (                                                                      l                  11                                                            0                                            0                                            0                                                                                      l                  21                                                                              l                  22                                                            0                                            0                                                                                      l                  31                                                                              l                  32                                                                              l                  33                                                            0                                                                                      l                  41                                                                              l                  42                                                                              l                  43                                                                              l                  44                                                              )                    
For generating elements of column 1 of L, the following calculations are performed in the order shown:l11=√{square root over (a11)}l21=a21/l11 l31=a31/l11 l41=a41/l11 For generating elements of column 2 of L, the following calculations are performed in the order shown:l22=√{square root over (a22−l21×l21*)} (where l21* denotes the conjugate of l21)l32=(a32−l31×l21*)/l22 l42=(a42−l41×l21*)/l22 For generating elements of column 3 of L, the following calculations are performed in the order shown:l33=√{square root over (a33−l31×l31*−l32×l32*)} (where l31* and l32* are the conjugates of l31 and l32, respectively)l43=(a43−l41×l31*−l42×l32*)/l22 For generating elements of column 4 of L, the following calculation is performed:l44=√{square root over (a44−l41×l41*−l42×l42*−l43×l43*)} (where l41*,l42*, and l43* are the conjugates of l41,l42, and l43, respectively)
Among other things, the inventors of the present invention have observed that the above generic order for calculating elements of the output matrix L may be modified to improve the throughput for generating the output matrix L.